#include <gtest/gtest.h>

#include <algorithm>
#include <vector>

#include "algorithm/datastruct/include/linker_operator.h"
using namespace std;
TEST(TestReverseLink, LinkerSuits) {
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(3);
    node1->next = node2;
    node2->next = node3;

    std::vector<int> std_res = {1, 2, 3};
    std::vector<int> res = travelList(node1);
    for (int i = 0; i < std_res.size(); i++) {
        EXPECT_EQ(res[i], std_res[i]);
    }
    ListNode *node = reverseList(node1);
    res = travelList(node);
    std::reverse(std_res.begin(), std_res.end());
    for (int i = 0; i < std_res.size(); i++) {
        EXPECT_EQ(res[i], std_res[i]);
    }
    delete node1;
    delete node2;
    delete node3;
}
TEST(TestMergeLink, LinkerSuits) {
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(3);
    ListNode *node3 = new ListNode(5);
    node1->next = node2;
    node2->next = node3;

    ListNode *node4 = new ListNode(2);
    ListNode *node5 = new ListNode(4);
    ListNode *node6 = new ListNode(6);
    node4->next = node5;
    node5->next = node6;

    std::vector<int> std_res = {1, 2, 3, 4, 5, 6};

    ListNode *head = mergeTwoListsRec(node1, node4);
    std::vector<int> res = travelList(head);
    for (int i = 0; i < std_res.size(); i++) {
        EXPECT_EQ(res[i], std_res[i]);
    }
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
}

TEST(TestFisrtCommonNode, LinkerSuits) {
    ListNode *node1 = new ListNode(0);
    ListNode *node2 = new ListNode(9);
    ListNode *node3 = new ListNode(1);
    ListNode *node4 = new ListNode(2);
    ListNode *node5 = new ListNode(4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    ListNode *node6 = new ListNode(3);
    node6->next = node4;

    ListNode *node = getIntersectionNode(node1, node6);
    EXPECT_TRUE(node);
    EXPECT_EQ(node->val, 2);
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
}

TEST(TestIsCycle, LinkerSuits) {
    ListNode *node1 = new ListNode(3);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(0);
    ListNode *node4 = new ListNode(4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2;

    bool res = hasCycle(node1);
    EXPECT_TRUE(res);
    node1->next = nullptr;
    EXPECT_FALSE(hasCycle(node1));
    delete node1;
    delete node2;
    delete node3;
    delete node4;
}

TEST(TestKthEnd, LinkerSuits) {
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(3);
    ListNode *node4 = new ListNode(4);
    ListNode *node5 = new ListNode(5);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    ListNode *res = getKthFromEnd(node1, 2);
    EXPECT_TRUE(res);
    EXPECT_EQ(res, node4);
    node1->next = nullptr;
    res = getKthFromEnd(node1, 2);
    EXPECT_FALSE(res);
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(TestIsisPalindrome, LinkerSuits) {
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(2);
    ListNode *node4 = new ListNode(3);
    ListNode *node5 = new ListNode(1);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    bool res = isPalindrome(node1);
    EXPECT_FALSE(res);
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(TestDeleteDuplicates, LinkerSuits) {
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(2);
    ListNode *node4 = new ListNode(3);
    ListNode *node5 = new ListNode(3);
    ListNode *node6 = new ListNode(4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;

    ListNode *res = deleteDuplicates(node1);
    std::vector<int> removeRep = travelList(res);
    std::vector<int> std_res = {1, 2, 3, 4};
    for (int i = 0; i < removeRep.size(); i++) {
        EXPECT_EQ(removeRep[i], std_res[i]);
    }

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
}

TEST(TestDeletekthEnd, LinkerSuits) {
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(2);
    ListNode *node4 = new ListNode(3);
    ListNode *node5 = new ListNode(3);
    ListNode *node6 = new ListNode(4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;

    ListNode *res = removeNthFromEnd(node1, 2);
    std::vector<int> removeRep = travelList(res);
    std::vector<int> std_res = {1, 2, 2, 3, 4};
    for (int i = 0; i < removeRep.size(); i++) {
        EXPECT_EQ(removeRep[i], std_res[i]);
    }
    node2->next = nullptr;
    res = removeNthFromEnd(node1, 2);
    EXPECT_EQ(res->val, 2);
    node1->next = nullptr;
    res = removeNthFromEnd(node1, 1);
    EXPECT_TRUE(!res);

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
}

TEST(TestRotateRight, LinkerSuits) {
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(3);
    ListNode *node4 = new ListNode(4);
    ListNode *node5 = new ListNode(5);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    ListNode *res = rotateRight(node1, 2);
    std::vector<int> rotated = travelList(res);
    std::vector<int> std_res = {4, 5, 1, 2, 3};
    for (int i = 0; i < rotated.size(); i++) {
        EXPECT_EQ(rotated[i], std_res[i]);
    }

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(TestEntryNodeOfLoop, LinkerSuits) {
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(3);
    ListNode *node4 = new ListNode(4);
    ListNode *node5 = new ListNode(5);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node3;

    ListNode *res = entryNodeOfLoop(node1);
    EXPECT_EQ(res->val, 3);
    node2->next = nullptr;
    res = entryNodeOfLoop(node1);
    EXPECT_EQ(res, nullptr);

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(TestSortList, LinkerSuits) {
    ListNode *node1 = new ListNode(4);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(1);
    ListNode *node4 = new ListNode(3);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    ListNode *sorted = sortList(node1);

    std::vector<int> sorted_res = travelList(sorted);
    vector<int> truth = {1, 2, 3, 4};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth[i], sorted_res[i]);
    }

    delete node1;
    delete node2;
    delete node3;
    delete node4;
}

TEST(TestReverseBetween, LinkerSuits) {
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(3);
    ListNode *node4 = new ListNode(4);
    ListNode *node5 = new ListNode(5);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    ListNode *sorted = reverseBetween(node1, 2, 4);

    std::vector<int> sorted_res = travelList(sorted);
    vector<int> truth = {1, 4, 3, 2, 5};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth[i], sorted_res[i]);
    }

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}
